//
// Created by 19281121-赵路路@BJTU on 2021/9/17.
//
#pragma once

#include <iostream>
#include <string>
#include <ctime>
#include <cmath>

using namespace std;

const long M = 26;
const long ROW = 8;
const long COL = 8;

long K[ROW][COL]; // encrypt matrix
long D[ROW][COL]; // decrypt matrix
long P[ROW] = {}; // plaintext unit
long C[ROW] = {}; // ciphertext unit
long F[ROW] = {}; // decryptedtext unit

struct GCD {
    long x;
    long y;
    long d;
};

void randomMatrix() {
    for (long i = 0; i < ROW; ++i) {
        for (long j = 0; j < COL; ++j) {
            K[i][j] = rand() % 26;
        }
    }
}

long detMatrix(long matrix[ROW][COL], long row) {
    long remainMatrix[ROW][COL];
    long remainRow;
    long p = 0, q = 0;
    long sum = 0;
    if (row == 1) {
        return matrix[0][0];
    }
    for (long i = 0; i < row; ++i) {
        for (remainRow = 0; remainRow < row - 1; ++remainRow) {
            if (remainRow < i) {
                p = 0;
            } else {
                p = 1;
            }
            for (long j = 0; j < row - 1; ++j) {
                remainMatrix[remainRow][j] = matrix[remainRow + p][1 + j];
            }
        }
        if (i % 2 == 0) {
            q = 1;
        } else {
            q = -1;
        }
        sum += q * (matrix[i][0] * (detMatrix(remainMatrix, row - 1) % 26) % 26);
        sum %= 26;
    }
    return sum;
}

long gcd(long a, long b) {
    if (a < 0) {
        a *= -1;
    }
    if (a < b) {
        long temp = a;
        a = b;
        b = temp;
    }
    return a % b == 0 ? b : gcd(b, a % b);
}

bool isInverse(long matrix[ROW][COL]) {
    if (gcd(detMatrix(matrix, ROW), M) == 1) {
        return true;
    } else {
        return false;
    }
}

void Multiply(long matrix[ROW][COL]) {
    memset(C, 0, sizeof(C));
    for (long i = 0; i < ROW; ++i) {
        for (long j = 0; j < COL; ++j) {
            C[i] += P[j] * matrix[j][i];
        }
    }
}

long mod(long a) {
    return a >= 0 ? a % M : (M + a % M);
}

string encryption(string str) {
    string result;
    memset(P, 0, sizeof(P));
    for (long i = 0; i < ROW; ++i) {
        P[i] = str[i] - 'a';
    }
    Multiply(K);
    for (long i = 0; i < ROW; ++i) {
        C[i] = mod(C[i]);
        result += C[i] + 'a';
    }
    return result;
}

void adjointMatrix(long matrix[ROW][COL]) {
    long p = 0;
    long q = 0;
    long temp[ROW][COL];
    memset(D, 0, sizeof(D));
    for (long i = 0; i < ROW; ++i) {
        for (long j = 0; j < ROW; ++j) {
            for (long k = 0; k < ROW - 1; ++k) {
                if (k < i) {
                    p = 0;
                } else {
                    p = 1;
                }
                for (long l = 0; l < ROW - 1; ++l) {
                    if (l < j) {
                        q = 0;
                    } else {
                        q = 1;
                    }
                    temp[k][l] = matrix[k + p][l + q];
                }
            }
            D[j][i] = (long)pow(-1, (double)i + j) * detMatrix(temp, ROW-1);
            D[j][i] = mod(D[j][i]);
        }
    }
}

GCD extendedEuclid(long a, long b) {
    GCD aa, bb;
    if (b == 0) {
        aa.x = 1;
        aa.y = 0;
        aa.d = a;
        return aa;
    } else {
        bb = extendedEuclid(b, a % b);
        aa.x = bb.y;
        aa.y = bb.x - (a / b) * bb.y;
        aa.d = bb.d;
    }
    return aa;
}

long inverse(long a, long m) {
    GCD aa;
    aa = extendedEuclid(a, m);
    return aa.x;
}

string decryption(string str) {
    string text;
    long determinant = detMatrix(K, ROW);
    long inver = inverse(determinant, 26);
    adjointMatrix(K);
    memset(F,0,sizeof(F));
    for (long i = 0; i < ROW; ++i) {
        for (long j = 0; j < ROW; ++j) {
            F[i] += C[j] * D[j][i];
        }
        F[i] *= inver;
        F[i] = mod(F[i]);
    }
    for (long i = 0; i < ROW; ++i) {
        text += F[i] + 'a';
    }
    return text;
}

void Hill() {
    // Matrix derive
    srand((unsigned) time(0));
    randomMatrix();
    while (!isInverse(K)) {
        randomMatrix();
    }
    cout << "******************************" << endl;
    cout << "Encryption matrix is:" << endl;
    for (long i = 0; i < ROW; ++i) {
        for (long j = 0; j < COL; ++j) {
            printf("%2ld  ",K[i][j]);
        }
        cout << endl;
    }
    cout << "******************************" << endl;
    cout << "The determinant of this matrix is "
    << detMatrix(K, ROW) << ", which interacts with 26." << endl;

    // Preparations
    string plainText;
    string cipherText;
    string decryptedText;

    // Inputs
    cout << "Please enter the string you want to encrypt(8 characters):" << endl;
    cin >> plainText;

    // Encrypt
    cipherText = encryption(plainText);
    cout << "The ciphertext is: " << cipherText << endl;

    //Decrypt
    decryptedText = decryption(cipherText);
    cout << "The decryptedtext is: " << decryptedText << endl;
}